package com.ayuer.chapter01;

import java.util.Arrays;

public class BinarySearchDemo {
    public static void main(String[] args) {

//        int[] arr01 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
//        int binaried01 = binarySearch(arr01, 2);
//        System.out.println(binaried01);

//        int[] arr02 = {1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10};
//        int binaried02 = binarySearchLeftMost(arr02, 4);
//        System.out.println(binaried02);

        int[] arr03 = {1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10, 12};
//        int[] arr03 = {1, 3, 5, 6};

        int binaried03 = binarySearchInsert(arr03, 11);
        System.out.println(binaried03);

    }

    //二分查找,找不到就进行插入
    public static int binarySearchInsert(int[] arr, int target) {
//        例如是11，当end>start的时候，说明，可以在该位置插入了，
//        如果大于值小于end的值
//        如果大于值大于end的值
//        int[] arr03 = {1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10, 12};

        //初始化指针
        int start = 0;
        int end = arr.length - 1;
        while (start <= end) {
            //中间指针
            int mid = start + (end - start) / 2;
            if (arr[mid] < target) {
                start = mid + 1;
            } else if (target < arr[mid]) {
                end = mid - 1;
            } else {
                return arr[mid];
            }
        }
        return start;


    }


    //二分查找leftMost
    public static int binarySearchLeftMost(int[] arr, int target) {

        //初始化指针
        int start = 0;
        int end = arr.length - 1;
        //最左侧的指向
        int leftMost = -1;
        while (start < end) {
            //中间指针
            int mid = (start + (end - start) / 2);
            if (arr[mid] < target) {
                start = mid + 1;
            } else if (target < arr[mid]) {
                end = mid - 1;
            } else {
                //记录此时的index
                leftMost = mid;
                //缩小边界
                end = mid - 1;
            }
        }
        return leftMost;
    }


    //二分查找
    public static int binarySearch(int[] arr, int target) {
        //初始化指针
        int start = 0;
        int end = arr.length - 1;
        while (start <= end) {
            //中间指针
            int mid = start + (end - start) / 2;
            if (arr[mid] < target) {
                start = mid + 1;
            } else if (target < arr[mid]) {
                end = mid - 1;
            } else {
                return arr[mid];
            }
        }
        return -1;
    }


}
